Aufgabe aus \buchmann{9.7.7} auf Seite 163: Wie viele Operationen erfordert die RSA-Verschlüsselung mit Verschlüsselungsexponent $e = 2 ^ {16} + 1$?

\textbf{Lösung}

Es gilt $c = m ^ {e} \tmod n$, wobei $c$, $m$, $e$, $n$ gegeben sind. Zur Berechnung wird die schnelle Exponentiation verwendet. Hinweis: Modulo-Operationen werden vernachlässigt.

\begin{enumerate}

\item Zuerst wird die Binärentwicklung von $e = 2 ^ {16} + 1$ erzeugt. Das ist hier obsolet, da $e$ bereits als Binärentwicklung vorliegt.

\item Anschließend werden die sukzessiven Quadrate berechnet für $\sum_{i=1}^{16}{m ^ {2 ^ {i}}}$. Dafür sind genau \textbf{16 Quadrierungen} notwendig.

\item Anschließend werden die sukzessiven Quadrate entsprechend der Binärentwicklung verkettet. Hierfür ist genau \textbf{1 Multiplikation} (wegen $2 ^ {16} + 1$).

\end{enumerate}

\begin{center}
\uuline{Es sind genau $17$ Rechenschritte notwendig}
\end{center}